Ray Casting

An dieser Stelle möchte ich Ray Casting entwickeln - also ein Labyrinth aus einer 2-D Matrix in eine 3-D Ansicht überführen. Vorbilder für den Atari gibt es ja einige - Project M, Doom etc..... am Ende darf eine allgemeine 3D Engine entstehen, die jeder benutzen kann... so der Plan!

Die Theorie ist relativ klar, schwierig wird die Umsetzung auf den Atari werden und da brauche ich Unterstützung. Hat jemand Erfahrung mit Ray Casting??

Ray Casting natürlich - gleich geändert. Ich würde das ohne Erweiterung machen, damit es kompatibel ist.

Als Erstes würde ich die 2-D Matrix für das Labyrinth erstellen aus der ja dann die Pseudo-3D Ansicht erstellt wird. Daher müsste man sich primär Gedanken machen, welche Antic Mode für unser Ray Casting wohl am besten geeignet ist. Wer hat da Erfahrung und eine Idee??

vielen Dank für die Inputs... leider nur Demos und gute Erklärungen - leider nirgends mal ein Code zum anschauen oder eine Art Engine für die Allgemeinheit. Jeder muss immer das Rad für sich neu erfinden... also dann!

super cool, vielen Dank erst einmal!!

.... nun hatte ich wenig Zeit in den letzten Tagen, möchte aber jetzt weiter voranschreiten ....

Als ersten Schritt muss ich jetzt eine einfache Matrix aufbauen. Ich fange mit vielleicht 20 x 20 an - hier werden zunächst nur entweder eine 0 oder eine 1 reinkommen. 1 bedeutet Wandelement und 0 bedeutet Luft - also freie Fläche.Irgendwo in dieser Matrix steht dann der Spieler und schaut zunächst nach Norden (das wäre dann in Richtung erste Reihe der Matrix) und hat ein Blickfeld welches definiert ist. Auf die Matrix muss ich einfach zugreifen können, da sie ständig abgefragt wird. Wenn der Blick nach vorne geht, dann muss ja quasi der Blickweg durchschritten werden und jedes einzelne Matrixfeld wird in Blickrichtung abgefragt. Es ist quasi als würde man eine Linie zeichnen, nur man zeichnet nichts, sondern liest die Matrix aus. Immer wenn man auf eine 1 stößt, wird dann an dieser Stelle ein Wandelement gezeichnet. Die x-Position der Matrix ist einfach auszulesen, bei der y-Position bin ich mir nicht sicher, wie ich das am einfachsten (schnellsten) mache...

hmmm... also ich muss ja den Raum quasi definieren und das wollte ich über eine .txt Datei machen (siehe Bild). Das geht auch - da muss ich dann halt immer vorher die y-Position so konvertieren, daß ich je nach Zeile entsprechend y0...y20 abfrage. Das klingt allerdings irgendwie umständlich und dadurch langsam und ich frage mich wie das schneller und eleganter gehen könnte...

Meine derzeitige Lösung wäre folgende:

an der Position x=7 und y=5 will ich die entsprechend hinterlegte Zahl 2 auslesen.

Eine kleine Konvertierungsroutine macht zunächst aus dem einfachen y Wert (hier 5) y5 und speichert das dann per selbstmodifizierenden Code an die Position der Abfrageroutine, wo dann mit lda y5,x die entsprechende Zahl (in diesem Falle 2) ausgelesen wird. Was besseres fällt mir jetzt nicht ein... klingt aber kompliziert und geht bestimmt mit MADS viel schneller und eleganter...

Hallo Janko, lieben Dank! Ja genau das habe ich gesucht. Supi!!

... gerade hänge ich an dem Problem des Field Of View.... Ein gutes FoV beim RayTr ist 60 Grad - wenn ich also von meinem Standort (der bekannt ist) schräg in Richtung Wand schaue, dann ist mein FoV 30 Grad nach links plus 30 Grad nach rechts. Meine Sehstrahlen müssen also x mal in die eine Richtung nach vorne "absuchen" und x mal in die andere Richtung nach vorne absuchen bis jeweils ca. 30 Grad erreicht sind. Das bedeutet die Winkel 30 Grad teilen sich jeweils in kleinere Teilwinkel auf - je nachdem wie weit weg ich von der Wand stehe. Das kann ich natürlich alles mathematisch berechnen, aber wir sprechen hier von arcTan und so weiter.....

Das muss doch einfacher gehen.... eine Art Näherung. Ich muss ja eigentlich nur wissen, wir oft ich (in Abhängigkeit der Entfernung von der Wand und der Senkrechten zur Wand) in zB 1er Schritten den Abtaststrahl nach links und nach rechts machen muss....

.... folgende Überlegung fällt mir dazu gerade ein: Ich befinde mich ja zunächst nur auf einer virtuellen Matrix. Diese Matrix analysiere ich und stelle sie dann auf dem Bildschirm dar. Die Breite des Bildschirmes bzw. des Ausschnittes, den ich darstelle, bildet mein FoV, meine Sichtlinie ist die Mitte des Bildschirmes, dadurch ist eigentlich immer auch genau definiert, wie oft ich nach links und rechts von der Hauptsichtlinie (die immer in der Mitte ist) in der Matrix gehen muss...

Hallo Erhard, es gibt ja genügend Literatur, was das Ray Casting angeht. Das Prinzip ist klar und auch die theoretische Umsetzung. Das Problem ist dann praktischer Natur: Wie baue ich das speziell auf einem Atari 8 Bit in Assembler. Die neueren Beispiele nutzen überwiegend C als Hochsprache oder haben spezielle Grafikprogramme. All das geht beim Atari nicht. Man muss das Prinzip extrem auf unsere kleine Kiste anpassen und dabei 3x um die Ecke denken. Fast alle Beispiele kochen ihre eigene Suppe und haben sicherlich ganz eigene knifflige und pfiffige Umsetzungen. Die entsprechenden Assemblercodes werden extrem komplex sein - jeder hat auch so seine Art zu programmieren - und so macht es wenig Sinn andere Autoren zu fragen... vor einem Jahr wollte ich die Softwaresprites lernen, hatte eine wirklich gute Vorlage und dann aber alles in die Ecke geworfen und es für mich komplett neu von Grund auf gemacht und so erlernt. Und das macht es ja auch aus. Ich möchte das hier entwickeln und alle Klippen umschiffen bzw. meistern - gerne mit Inputs von anderen Programmierern - und daraus am Ende was schönes zu bauen... Liebe Grüße Peter

Hi Erhard, ich verstehe das ja, aber mittlerweile habe ich mich tief in die Assemblerprogrammierung des Ataris eingearbeitet... mein Programmierstil ist auch anders, glaube ich, da ich mir alles selber erarbeitet habe und die Profis in der Regel aus der C++ am besten noch objektorientiert herkommen. Das merke ich immer, wenn ich mich mit Janko austausche, der das halt professionell gelernt hat und ich aber was das angeht ganz anders programmiere... andere Codes zu lesen finde ich eher schwierig. Das Thema der 3D ist so kompliziert, ich kann mir echt nicht vorstellen, daß ich da einen fremden Code so richtig durchdringe. Außerdem erlerne ich solche Dinge auch selber gerne und schöpfe daraus meine Befriedigung. Ich versuche bis zur Fujiama ein wenig weiterzukommen und dort gibt es massiv know how ... alleine die Gespräche mit Peter werden in dieser Hinsicht sicherlich weiterführen - darauf freue ich mich schon ganz besonders! Aber auch auf die M.U.L.E. Zockabende und einfach auf 5 tolle Tage! Kommst du eigentlich auch? LG Peter

... ja, das werde ich mit einer Tabelle machen... oder mir fällt etwas viel einfacheres ein. Ich habe da eine Idee, die Frage ist nur, wie das nachher aussieht.

... heute habe ich mich noch sehr viel mit Grundlagen beschäftigt und war erstaunt, was es alles so "gibt". Zunächst war mir klar, daß ich ja zur Berechnung des Blickpunktes bis zur 1. Wand den Satz des Pythagoras benötigen werde. Hier muss ich quadrieren, was kein größeres Problem darstellt und dann aber die Wurzel ziehen. Eine Iteration macht es möglich das auszurechnen - nur das Problem ist die vorherige Quadrierung, denn ruck zuck ist man über 255 und schon braucht man eine 16 Bit - Zahl. Also habe ich ein paar Ideen entwickelt, wie man das Problem umgehen kann - und das funktioniert auch. Hier würde ich einige Tabellen brauchen und dann eine gute Näherung während des Bresenham-Zuges für die Distanz hinbekommen. Dann habe ich mich mal umgeschaut, ob es nicht eine Iteration bzw. Näherung gleich für den ganzen Pythagoras gibt - und siehe da, die Lösung ist so easy: Aus cc = aa+b*b wird einfach: c = a + b/2 , wobei b dann die kürzere Seite ist. Jetzt kann ich loslegen:

Die 4 Bresenham-Routinen reinbauen, um den Weg vom Betrachter zu einem virtuellen Punkt zu detektieren (auf der Matrix) - sobald ein Wert > 0 gefunden wurde bricht dieser Strahl ab, die Länge wird berechnet und je nach Länge wird die Wand entsprechend groß oder klein gezeichnet. Dann kommt der nächste Sichtstrahl usw. bis das ganze FoV abgearbeitet wurde. Ich denke ich werde mit zwei Bildschirmen arbeiten, damit immer nur im nicht sichtbaren Bereich gezeichnet wird.... auf gehts...

... eine erste kleine noch sehr rudimentäre Umsetzung habe ich jetzt realisiert. Alles noch ohne Größenperspektive und Drehung - aber schon mal ein begrenztes Field of View mit Umsetzung einer 2D Matrix in eine 3D Perspektive...

Als nächstes werde ich die Größen in Abhängigkeit der Entfernung zu den Wandteilen umsetzen, dann kommen die ersten Bewegungen...

... ein weiteres kleines Update... Ich muss sagen, die Umsetzung ist nicht einfach!! Tatsächlich schaffe ich es jetzt schon, relativ einfache Wände auch verschieden farbig darzustellen. Die Perspektive stimmt noch nicht - da ist echte Handarbeit nötig, damit die Wände alle in der richtigen Größe je nach Abstand zum Beobachter stehen. Auch die schrägen Linien sind noch zu grob... kann man alles machen, kostet aber Rechenzeit, die schnell weg ist.... Noch wirkt alles irgendwie ruckelig und nicht gut aufgelöst - aber immerhin schaffe ich jetzt schon einen Rundumblick... alles ist vorbereitet, um durch die Matrix zu gehen und die Wände und Dinge entsprechend darzustellen. Am Ende muss ich sehen, ob es für ein Game reicht, oder ob das hier nur so eine Art Machbarkeitsstudie wird...

Hallo Erhard, das stimmt natürlich. Die Tabelle wird aber noch andere Elemente bekommen. Und dennoch macht eine Kompression evt. später Sinn - wobei ich mich mit der Kompression gar nicht auskenne und das daher meide. Insgesamt wäre das 3D Game (wenn ich es überhaupt realisieren kann) auf einen XE mit 128 kB ausgerichtet. Da sollte dann genug Platz für die Matrix sein... Im Moment habe ich aber noch ganz andere Probleme: Der Schwenk nach rechts und links funktioniert nur für einen Teilausschnitt - sobald ich an die rechte oder linke Matrixwand stoße bekomme ich Fehler (was logisch ist), hier ist noch ein wenig Hirnschmalz und Code nötig. Mein derzeitiges größtes Problem ist allerdings die nicht stimmende Perspektive. Im Prinzip macht er, was ich will - allerdings dann doch nicht . Es liegt an der Berechnung des Abstandes vom Betrachter zur jeweiligen Wand und dann die Umsetzung: Weiter Abstand / kleine Wand, naher Abstand / große Wand. Hier muss ich noch richtig viel tun, damit es gut aussieht... vielleicht scheitere ich auch daran... Liebe Grüße Peter

absolut... ich denke am WE werde ich mir das mal genau auf einem Blatt aufmalen und dann die Entfernungen ausrechnen und entsprechend die Perspektiven danach anschauen und berechnen... das dann evt. in einer Tabelle umsetzen...

... das habe ich jetzt mal getan und alles neu berechnet:

und dabei ist für die Darstellung der entsprechenden Wandteile in Abhängigkeit von der Perspektive und des jeweiligen Sichtstrahles eine für mich neues Formel rausgekommen: P(x / y0-d+dx/2) x ist die horizontale Position der Wand, die y-Position der Wand berechnet sich aus der y-Position des Players minus der Perspektive d - also der Entfernung des Betrachters zur Wand plus der Abstand Betrachter zur Wand in x-Richtung durch 2... läßt sich alles super einfach berechnen! Folgende erste Umsetzung ist dabei bereits herausbekommen:

Das ist bereits jetzt echtes Ray-Casting. Probleme gibt es noch mit der Drehung und dem Schwenk nach rechts und links. Die Wandteile sind bislang einfarbig und ich habe bislang nur 2 Farben eingesetzt, das kann man aber leicht erweitern. Der Bildaufbau ist insgesamt noch ruckelig... da fällt mir aber sicherlich noch einiges an Optimierungen ein und die Tabelle mit der Perspektive muss ich noch optimieren...

... ein weiteres Problem ist mir jetzt gerade klar geworden: Im Prinzip schaue ich die ganze Zeit nach vorne (in der Matrix nach oben) und beziehe mich bei dem FoV auf die x-Werte und lasse dann meinen jeweiligen Sichtstrahl z.B. von x=5 bis x=25 wandern. Das funktioniert. Wenn ich nach rechts schwenke, dann geht der x-Bereich entsprechend nach rechts oder links mit. Die Bewegung nach vorne bzw. nach hinten läuft ähnlich, es wird der jeweilige y-Wert incrementiert oder decrementiert... das ist natürlich nicht korrekt und spätestens wenn ich an den linken oder rechten Rand stoße, dann geht es nicht mehr. Die komplette Rotation funktioniert entsprechend auch gar nicht. Im Grunde muss ich es so programmieren, daß ich mich völlig frei in der Matrix bewegen kann und sich das FoV (field of view) immer nach der jeweiligen Blickrichtung ausrichtet.... hat da jemand Erfahrung mit? Wahrscheinlich komme ich nun doch nicht an Winkeln mit sin cos etc. vorbei....

Guten Morgen Erhard, ja in der Tat wundert einen das so manchmal. Nun muss man allerdings bedenken, daß die allermeisten dieser Programme in C geschrieben werden und die Befehle dort einfach viel mächtiger sind, als in Assembler. Irgendwelche komplexen Fließkommaberechnungen mit Winkelfunktionen etc. gehen da mit einer Kommandozeile und laufen sehr schnell ab, in Assembler - und gerade auf unserem alten A8 - muss man alles quasi neu erfinden und optimieren. Theoretisch könnte man relativ einfach einen Raycaster in Basic schreiben, dann kannst du aber zusehen wie die Pixel gemütlich über den Screen stolpern 😉

Ich habe ja einen täglichen Arbeitsweg von 2x45 Minuten und verbringe diese Zeit sehr oft zum Grübeln... und im Kopf habe ich nun eigentlich alle Lösungen für meinen Raycaster parat. Eigentlich ist es relativ simple - so far ....

Es gibt 2 Ebenen: Die erste Ebene - die nicht sichtbare Ebene - ist die Matrix. Hier sind alle Informationen der Landschaft enthalten und auch nur hier bewege ich mich und hier "arbeite" ich. Die andere Ebene ist die des Bildschirmes. Diese Ebene ist simpel. Ich habe einen definierten Bildausschnitt und in diesen Bildausschnitt printe ich die ganze Zeit mein FieldOfView. Die Position des Betrachters in Bezug auf den Bildschirm ist immer gleich. In der Mitte. Der linke Rand des Bildschirmes ist der linke Rand meines FoV und entsprechend der rechte Rand rechts. Nun brauche ich nur noch den Abstand von mir und dem Objekt und die jeweilige x- und y-Position - und das erhalte ich direkt aus der Matrix!

Eigentlich muss ich mich also fast nur um die Matrix kümmern. In der Matrix hat der Player eine bestimmt x- und y-Position. Um den Player herum werde ich in einer Tabelle einen relativ großen Kreis spannen. Der Kreis ist virtuell, hat dabei aber eine klare Nord-Süd-Ausrichtung genau wie die Matrix. Meine Blickrichtung bezieht sich auf den Kreis und je nachdem wo ich auf dem Kreis bin (ich werde das winkelabhängig festlegen) wird eine Tabelle abgefragt. Hier werde ich dann entsprechende Werte hinterlegen in wie weit man in x- bzw. y-Richtung zu laufen hat. Im Grunde ist das dann die Steigung einer virtuellen Geraden in Blickrichtung - mein Sichtstrahl. Konkret bedeutet das z.B.: wenn ich für den Kreis 72 mögliche Positionen festlege, dann wandert der Blick jeweils um 5 Grad weiter, auf Position 9 steht der Blick bei 45 Grad, die Tabelle würde jetzt für x und y den Wert 1 ausgeben, also ein Schritt in x-Richtung und ein Schritt in y-Richtung, jeweils vom Ausgangspunkt des Players. Trifft man auf ein Hindernis der Matrix, stoppt der Sichtstrahl und die Position und der Abstand wird berechnet und dann auf den Bildschirm geprintet. Der Abstand wird mit Pythagoras berechnet und hier nehme ich die bekannte einfacher Näherung c=a+b/2, b<a Die Bewegung erfolgt auch in der Matrix und geht immer nur nach vorne oder nach hinten und dann in Abhängigkeit des einen Sichtstrahls genau in der Mitte des FoV.

Damit habe ich alles (im Kopf) und muss das jetzt nun noch umsetzen. Den ganzen Bresenham-Algorithmus oder das Zeichnen schneller Linien mit viel Rechenzeit brauche ich damit nicht mehr...

Mein Ziel ist es am Ende natürlich einen Raycaster für mich zu entwickeln, aber auch eine relativ einfache Engine für alle zu bauen. Dann muss man nur noch die Matrix erstellen und kann die dann 3D auf den Bildschirm über die Engine ausgeben...

Gruß Peter

P.s. Dieses Thema wird relativ wenig kommentiert. Liegt es daran weil es zu speziell oder kompliziert ist?

... danke für die Rückmeldungen... das Flackern sehe ich auch und verstehe ich nicht 😂 - muss aber eh alles komplett neu überarbeitet werden, da der alte Ansatz zwar schon recht gut funktioniert, aber doch in eine Sackgasse führt. Ich werde fast alles komplett neu stricken müssen (und freue mich schon drauf!!).

Eigentlich echt interessant - ähnlich wie letztes Jahr wo ich die Softwaresprites in Angriff genommen hatte - jetzt das Ray-Casting... bin ich jetzt so langsam dabei das Thema zu durchdringen (ok -wie das mit den Texturen geht... das bekommen wir später) und am Anfang komplett ahnungslos, zwischendurch frustriert und mehrfach so weit das Projekt zu stoppen und aufzugeben. Aber nach vielen Wochen komme ich so langsam dahinter und bin mittlerweile richtig zuversichtlich, daß ich am Ende alle Klippen meistern werde.

So in noch etwas größerer Ferne winken die Themen wie: Texturen, animierte Gegener/Schüsse - alles natürlich in korrekter Perspektive in 3D.... das wird richtig tricky!!

Eines noch zum Flackern: Wenn alles läuft - also die Drehung und Bewegung nach vorne und hinten mit Kollisionsabfragen, werde ich den eigentlichen Printvorgang wohl wieder mittels zweier Bildschirmen realisieren. Der Printvorgang läuft dann jeweils im nicht sichtbaren Bereich und erst wenn das komplette FoV gezeichnet wurde, wird entsprechend umgeschaltet. Beide Bildschirmbereiche will ich in eine eigene Bank legen, wo dann der Grafikchip direkt zugreifen kann... so der Plan

das Programm wird sicher wieder allen Speicher kosten und daher plane ich es wieder direkt für den 130 xe

Leider hatte ich da doch noch einen kleinen Denkfehler, denn auch ich kann die Physik / Mathe nicht austricksen... jedenfalls nicht komplett. Für die ganzen Berechnungen in der Matrix bleibt es wie es ist. Für die Darstellung auf dem Bildschirm brauche ich zwingend sin und cos!! Aus der Matrix generiere ich ja nur den Abstand des Betrachters zum Gegenstand/zur Wand in Abhängigkeit vom Blickwinkel 0 Grad. Für den Bildschirmprint benötige ich aber die Position in x und y-Richtung zum Hauptsichtstrahl - dieser ist ja immer fix und auch die Position des Betrachters zum Bildschirm bleibt immer gleich und fix. Das gesamte FoV rotiert oder kommt näher, oder weiter weg und nicht der Betrachter selber... also in der Matrix bewege ich mich, die eigentliche Darstellung des sich immer ändernden FoV auf den Bildschirm muss aber so erfolgen, daß alle Objekte quasi bewegen... klingt kompliziert. Na jedenfalls brauche ich den Abstand a und b (was nix anderes ist als x und y für die Bidschirmausgabe des Objektes. Demnach ist dann a = d * cos alpha und b = d * sin alpha

Weil man das in Assembler nicht gut rechnen kann, mache ich also eine weitere Tabelle für jeweils 8 verschiedene Winkel und 30 verschiedenen Abständen d (von 0-30). Verbraucht dann nochmals ca. 500 Bytes....

Hier die ersten Werte:

Die ganze Sache ist schon wirklich kompliziert.....

das mache ich doch alles für euch hier 😉

Als alter Hobbymathematiker bin ich allerdings Geodreieck, Rechner und Bleistift gewöhnt und finde das für mich auf einem Blatt Papier immens plastisch, anschaulich 😉

der Link ist natürlich super... vielen Dank dafür!

... tatsächlich habe ich damals schon wegen eines progressiven Mathelehrers als einer der Ersten mit einem TI Taschenrechner rechnen dürfen. Dieser hatte sogar schon erste Programmierfunktionen... Damals hatte ich aber den alten Rechenschieber meines Vaters irgendwo gefunden und mich mal damit beschäftigt... geht!!!

Manche Dinge muss man einfach auch pragmatisch sehen! Wenn ich schon dabei bin die Mathematik zu meinen Problemen geometrisch und arithmetisch auf einem Zettel herzuleiten, dann kann ich auch schnell ein paar Zahlen berechnen. Die Zahlen habe ich dann direkt auf dem Zettel und kann sie später dann in mein Programm übertragen. Manchmal geht das händisch tatsächlich schneller. Alternativ hätte ich natürlich auch ein kleines Programm mit Atari Basic machen können... oder eine Numbers Tabelle. Ich wette insgesamt wäre es mit den paar Zahlen nicht schneller gewesen 😉

Ich mache ja fast alles digital, manche Dinge sind aber analog auch gut und evt. sogar übersichtlicher...

.... ich habe das jetzt mal aus Spaß versucht umzusetzen: Excel ist echt gut und früher habe ich damit viel und gerne gearbeitet... das war mit Abstand beste Programm von Microsoft!! Numbers von Apple stinkt da echt ab. Ich habe nur Numbers. Die benötigte Integer Funktion habe ich nicht gefunden, daher gestaltet sich die Tabelle zunächst schwierig. Habe ich dann aufgegeben. Dann habe ich ein kleines Programm in Atari Basic geschrieben. Die doppelte Schleife war einfach programmiert, gibt aber für Sinus falsche Werte aus... keine Ahnung warum. Insgesamt rechne ich es zu Fuss, weil es nicht viel zu rechnen ist und mir tatsächlich Zeit spart...

... ok ... also Atari Basic ist auf Bogenmaß eingestellt! Mit DEG stellt man auf Grad um und dann kommen auch die korrekten Werte raus...

Die Tabellenfunktion von Numbers ist ebenfalls auf Bogenmaß eingestellt - die Umstellung auf Grad ist echt mega umständlich - die Integer - Funktion heißt "ABRUNDEN" - wie blöd ist das denn.... also wenn mir was fehlt bei Apple dann ist echt mindestens Excel......

... open office ... 😉

Hallo und guten Morgen Lars, sehr interessanter Aspekt mit der Matrix und den Punkten... werde ich mal durchdenken. Eigentlich war mein jetziger Ansatz ganz ähnlich. Ich betrachte einen 1/4 Kreis - also von 0-90 Grad und lege für jeweils plus 2,5 Grad die entsprechenden Wege in Blickrichtung fest. Für eine Blickrichtung könnte das z.B. folgende Logik sein: 1,2,1,2,1,3,1,2,1,4... dann wieder die gleiche Folge. Der erste Wert geht in x-Richtung und der 2. in y-Richtung. Bei jedem Step wird geschaut, ob ein Hindernis vorliegt. Wenn ein Hindernis kommt, stoppt die Blickrichtung sofort und die nächste wird ausgeführt. Ich muss noch schauen bei dieser Methode, ob es blinde Flecken geben kann - vielleicht ist da deine Methode besser...

Das Problem kommt jetzt leider aber erst noch und das war mir immer nie so richtig klar: Die x- und y-Werte der Matrix kann ich nicht so einfach für die Wiedergabe auf den Bildschirm nutzen. Die Blickrichtung in der Matrix ist ja immer verschieden wenn man sich dreht - und das tut man ständig - die Blickrichtung auf dem Bildschirm ist immer ganz fix nach vorne - um nun die x- und y-Positionen bei einem Treffer in der Matrix auf die Position auf dem Bildschirm darzustellen muss ich es mit sin und cos umrechnen. Es sei denn ich habe gerade einen Knoten in der Denke und / oder es geht noch viel einfacher... LG Peter

... nach 2 Wochen im Camper quer durch Südeuropa und nach über 4000 Km nun zurück. Eine Woche arbeiten und dann ist endlich die Fujiama!! Vorher werde ich endlich mein Projekt weiter entwickeln - es gibt viel zu tun - und dann auf der Fuji programmieren programmieren programmieren... freue mich total auf die Zeit mit Euch...

... jetzt habe ich 2650 Bytes dafür investiert, um den Bresenham - Algorithmus zu ersetzen. Insgesamt 140 Draw-Anweisungen in einer Tabelle und je nach Blickwinkel von 0-360 Grad in 2,5 Grad-Schritten kommen dann die entsprechenden Anweisungen der Schritte in x- bzw. y-Richtung zur Anwendung. Einen Endpunkt des jeweiligen Sehstrahls gibt es nicht, lediglich wenn man beim Auslesen auf eine Zahl größer Null trifft, wird der Sehstrahl beendet, die Informationen berechnet und abgespeichert. Dann kommt der nächste Sehstrahl, bis das gesamte FoV abgearbeitet ist.
Alle Werte werden für die spätere Bildschirmausgabe berechnet (Sinus / Cosinus) und in Variablen gespeichert und wenn das FoV abgearbeitet ist am Stück geprintet. Insgesamt erhoffe ich mir damit deutliche Geschwindigkeitsvorteile bei der Bilderstellung und auch insgesamt, da ich nun nichts mehr mit Bresenham berechnen muss. Außerdem war das notwendig, da der Betrachter ja in der Matrix sich bewegt und der virtuelle 0-360 Grad Blickwinkelkreis ebenfalls. Bei Bresenham brauche ich ja immer einen definierten Start und ein definiertes Ende, was ich so nicht habe und aufwendig mitberechnen müsste. Das fällt weg.

Als nächstes erstelle ich noch eine umfangreiche Tabelle für die Sinus und Cosinus Berechnungen... dann müsste ich es haben!!

... nun habe ich die Sinustabelle eingefügt, darin sind die Werte enthalten für die Berechnung der x-Position der gefundenen Wand in Abhängigkeit vom Winkel zum Hauptsichtstrahl (0 Grad) und dem Abstand d vom Betrachter (Player) und dem getroffenen Wandteil. Dabei habe ich d-Werte von 0-50 und Winkel 2,5-22,5 Grad genommen. Das kostet mich nun also ca. ein halbes Kilobyte.

Als nächstes wollte ich die Cosinustabelle entsprechend reinbringen.. und siehe da: Die Werte für Winkel zwischen 0-22,5 Grad unterscheiden sich kaum. Cos 2,5 = 0,999 und Cos 22,5 = 0,92 Selbst bei einem maximalen Abstand von d=50 habe ich für den somit berechneten y-Werte nur eine Differenz von 4, bei kleineren Werten kann man fast sagen: d = y

Hier kann ich bestimmt eine schnelle Näherung reinbringen!!

.... endlich hatte ich auf der Fujiama Zeit mich konzentriert mit der Umsetzung des neues Algorithmus zu beschäftigen. Mein eigener Bresenham liegt nun in Tabellen und der Rundumblick mit Bewegung ist so möglich und das habe ich nun umgesetzt. Leider trat ein sehr hartnäckiger Bug auf, an dem ich mehrere Tage und Stunden rumgesucht habe. Letztlich konnte ich es am letzten Tag weiter eingrenzen und heute fiel der Groschen... mit einem sehr smarten Trick ist es mir gelungen, den Rundumblick nun vollständig durchzuführen und dabei nach vorne zu laufen. Damit ich das alles besser sehen und kontrollieren kann, habe ich unter dem Fenster eine Art Radar eingebaut, wo man praktisch von oben auf die Matrix schaut und wo die Blickrichtung dargestellt wird. Die Matrix ist dabei allerdings in y-Richtung stark gestaucht, daher läuft die Drehung nur scheinbar in unterschiedlicher Rotationsgeschwindigkeit. Die Wände werden jetzt auch richtig dimensioniert dargestellt, am Ende werde ich hier aber noch ein wenig optimieren müssen. Leider passt die Auflösung nicht so gut und gerade bei schrägen Wänden wird der obere und untere Rand zu grob - daher stelle ich als nächstes von GTIA 10 mit 9 Farben wieder auf ANTIC 5 mit 4 Farben um, da bekomme ich die Auflösung in x-Richtung besser hin.

Hier noch ein kleines Video:

.... TempleOfEris sollte Teil 3 meiner Programmreihe werden. Ursprünglich wollte ich einen weiteren Shooter mach, diesmal aber als Jump´n Run Spiel, wo man durch eine Art Höhlensystem zur Alienqueen vorstossen muss und diese dann final besiegen muss. Irgendwie bin ich dann auf diese Idee gekommen es 3D zu machen. Zuerst habe ich mich mit Vektorgrafik beschäftigt und viel über den Bresenhamalgorithmus gelernt, danach habe ich dann gesehen, daß man mit Ray-Casting alles viel besser machen könnte. Das wollte ich lernen und umsetzen. Mir war dabei immer klar, wie schwierig und anspruchsvoll das Thema ist - aber nach jetzt fast 5 Monaten kann ich stolz sagen: Es geht und ich habe das Ray-Casting umsetzen können!! Leider fehlt noch ganz viel: 1. Ein Bug hat mich viele Tage mehr als gequält und nun endlich habe ich ihn fast beseitigen können - durch einen Trick. Es funktioniert aber nicht vollständig. 2. Die Auflösung passt einerseits gut (9 Farben, die ich auch brauche), aber in x-Richtung bin ich eigentlich zu grob. 3. Die schrägen Wände sehen nicht wirklich gut aus, eine richt schön gezogene Wand bekomme ich noch nicht gut hin, da war ich mit der Vektorgrafik schon deutlich weiter. 4. Die Textur habe ich noch gar nicht bearbeitet und ehrlich gesagt, da habe ich noch fast keine guten Ideen. 5. Die Gegner mit Animation, Schuss und Perspektive... da bin ich noch meilenweit weg.

Wenn ich jetzt jeden Tag 3-7 Stunden am Projekt rumtüfteln würde, würde ich vielleicht in den nächsten 6 Monaten fast alle Probleme in den Griff bekommen - ob es dann vergleichbar gut wäre wie zB. Doom oder Projekt M oder Way Out ... glaube ich nicht!!! Daher lege ich das jetzt auf Eis!

Jetzt werde ich die späten Sommertage noch geniessen und mir überlegen, was ich als nächstes mache.... vielleicht ein kleines Projekt!

Liebe Grüße Peter

... nach Rücksprache mit meinem Kumpel und Freund Janko, habe ich beschlossen das Projekt hier zu pausieren und doch nicht zu beenden.... ich werde erstmal etwas anderes starten und dann irgendwann ohne Druck an meinem Raycaster weiter arbeiten...

... vorgestern bin ich um 5 Uhr aufgewacht und konnte nicht mehr einschlafen, da meine Gedanken die ganze Zeit um meinen Raycaster kreisten. Ihr kennt das sicherlich, wenn man die ganze Zeit im Kopf Lösungsmöglichkeiten für Probleme durchgeht... na jedenfalls bin ich gestern und heute nochmal alle mathematischen Dinge durchgegangen - alles stimmt soweit. Nur bei der Berechnung der Höhe der Wände habe ich noch große Probleme gehabt. Da passte fast nichts! Ich muss ja nach berechneter Distanz diese umkehren und dann mit irgendeinem Wert multiplizieren je nach erwünschter Wandhöhe. Das habe ich aber gar nicht mathematisch gemacht, sondern nach Auge / Gefühl. Jetzt bin ich die ganze Logik nochmal durchgegangen und habe aus d die entsprechende Höhe mit H = 1/d * 80 neu berechnet - vielleicht ist 80 noch zu wenig, da probiere ich ein wenig rum. Dann muss man noch die Distorsion rausrechnen. Die Distorsion bewirkt eine Verzerrung, da die Distanzen unbedingt parallel zum Hauptsichtvektor zu bestimmen sind und man ja durch den Blickwinkel der einzelnen Sichtstrahlen eine etwas zu große Distanz bekommt (siehe Bild).

Wenn d0 die gefundene Distanz zur Wand ist, dann muss man die Verzerrung noch rausrechnen: d = d0 * cos alpha Je größer der Winkel, desto größer die Verzerrung. In meinem Fall habe ich ja ein FoV von insgesamt 40 Grad - also jeweils 20 Grad nach links oder rechts vom Hauptsichtstrahl. Cos 20 = 0,94 .... die Verzerrung ist also nicht stark. Ich werde die Verzerrung aber in die Tabelle einrechnen, da ich 8 Sichtstrahlen habe, muss ich also dann für jeden Sichtstrahl eine eigene Tabelle anlegen, damit ich den cos nicht berechnen muss ... das ist dann ja in der Tabelle berechnet!

Ihr seht also: Ich komme von dem Thema kaum los, bin schon weit und komme auch voran und mache hier dann doch weiter!!

Was folgt nun: Ich muss einiges umbauen!

1. Ich muss 8 Tabellen ausrechnen, für jeden Sichtstrahl eine eigene Tabelle.
2. Die Abfragelogik anpassen - jetzt gehe ich von Sichtstrahl -20 aus und lauf bis +20. In Zukunft starte ich vom Sichtstrahl 0 und laufe erst bis -20 und dann von 0 bis +20
3. Bewegung nach hinten möglich machen.
4. Kollisionsabfrage - wenn der Player auf eine Wand trifft, bleibt er davor stehen.
5. Die Graphik anpassen - 256 Farben möglich machen.
6. Die Texturen reinbringen.
7. Die Matrix ausbauen.
8. Gegner reinbringen.
9. .......

LG und ein schönes WE Peter

Jetzt habe ich die Tabelle angepasst und entsprechend die Abstände korrigiert und die Distorsion raus. Die Bewegung geht jetzt auch nach hinten, die Kollisionserkennung ist drin, d.h. geht man vor eine Wand, bleibt man da einfach stehen und läuft nicht durch. Als nächstes muss ich noch die Ausnahme der "nahen Wand" fixen... in einigen Fällen detektiert er vor einer sehr nahen Wand einen Wandteil mit mehreren Sichtstrahlen und zeichnet diese Wand in gleicher Höhe mehrmal - das sieht blöd aus. Das muss ich abfangen... Danach baue ich die DL etwas um, damit ich 256 Farben bekomme... dafür nehme ich eine Vorlage, die ich von Janko bekommen habe - und dann kommt das große Thema der Texturen. Die vielen Farben brauche ich, um die Texturen schön hinzubekommen. Das wird sicherlich nochmal extrem schwer.... Immerhin habe ich jetzt aber die Ray-Cast-Engine so weit, daß sie wirklich sehr gut funktioniert!! Am Ende wird es noch jede Menge Feintuning geben - aber Rom ist ja auch nicht an einem Tag erbaut worden und außerdem sind wir Weltmeister 😉 LG

... man kann sich jetzt komplett frei durch die Matrix bewegen, nach links und nach rechts drehen, dabei nach vorne und auch nach hinten laufen. Wenn man vo einer Wand steht, dann bleibt man stehen und läuft nicht durch. Ich habe die Farben angepasst - jetzt schalte ich per DLI zwischen GTIA 9 und 11 und kann somit 256 Farben darstellen. Das will ich für Schattierungen der Wände nutzen. Als nächstes baue ich noch den Wandplot um - ich werde alle Daten für die FoV-Matrixauslesung sammeln und speichern, danach wird der komplette Bildschirm an einem Stück gezeichnet. Das wird die Bewegung stabiler machen. Danach geht es an die Texturen. Da habe ich bereits einige Ideen...

Anbei der letzte Stand des Raycasters:

... also die Streifen entstehen, wenn man 256 Farben haben will und quasi ständig zwischen 2 Grafikmodi schaltet. Die verschiedenen Farben entstehen dann quasi durch eine Art Teilfusion (Artifacting) der Scanzeilen. Das ist also erstmal so gewollt. Vielleicht baue ich das auch wieder um, wenn es zu sehr stört und ich die ganzen Farben so nicht brauche. Hier mal ein Bild von Projekt M (kann man auch bei youtube anschauen), wo die das ähnlich machen:

Die Wand wird manchmal noch nicht ganz korrekt erkannt und in diesem Fall wohl etwas zu groß gezeichnet, daher denkt man sie steht raus.... da muss ich noch einiges an Fehlern abfangen! Das Thema ist und bleibt tricky.....

Heute habe ich mir mal erste tiefere Gedanken über die Wandtextur gemacht und auf dem Sofa einige Ideen gesammelt....

Ich werde es so machen:
Ich möchte zunächst ähnlich wie bei Wolfenstein eine Steinwand/Felswand bauen. Die Farben (grau) mit verschiedenen Schattierungen habe ich ja durch das Mischen von GTIA 9+11... nun ist die Frage, wie man die Wände perspektivisch zeichnet und je nach Abstand die gleiche Wand größer und kleiner wird. Ich werde ca. 15-20 verschiedene Wandstreifen erstellen, die zusammengesetzt nebeneinander ein Steinmuster ergeben. Jeder Wandstreifen hat eine gewisse Basishöhe und hat ein Muster, welches quasi aus einzelnen horizontalen Linien besteht. Je nach Entfernung zur Wand besteht dann ein Wandstreifen aus diesen Linien, die dann aber nicht einmal sondern mehrmals gezeichnet werden - so wird dieser Wandstreifen dann entsprechend höher oder weniger hoch, behält aber sein Muster. Ich kalkuliere für jeden Wandstreifen ca. maximal 6-30 Bytes also im Mittel vielleicht ca. 20 Bytes - bei 20 Steifen sind das ca. 400 Bytes an Daten. Dazu kommt noch für jeden Streifen die verschiedene Größe je nach Entfernung - 400 * 40 = 16 kB also eine komplette Bank für die Wändtextur. Dazu kommen später noch Tore und weitere Items... Aber erstmal die Wandtextur!!

Hallo Mathy, ja der Link wurde erwähnt und ist mir bekannt. Es gibt viele interessante Informationen zum Ray Casting - auch gute Beispiele für den A8 mit echt tollen Umsetzungen, leider kocht da jeder so seine eigene Suppe und läßt wenig Infos raus, wie man das am besten speziell für den A8 macht.

Gerade jetzt stoße ich auf das nächste Problem und finde da so gut wie keine Informationen zum A8: Die Texturen!

Mittlerweile verstehe ich ganz gut, wie das funktionieren kann und wie es andere für den A8 gemacht haben. Es gibt aber noch ein paar Probleme. Hauptproblem ist wohl, daß angrenzende Sichtstrahlen ein Wandteil mehrfach treffen können und dieser dann entsprechend mehrfach gezeichnet wird. Für eine einfarbige Wand kein Problem - das tritt ja auch nur bei nahen Wänden auf und entsprechend der Nähe wird die Wand höher und breiter gezeichnet, allerdings würde das bei einer Textur blöd aussehen. Ich muss also genau wissen welcher Sichtstrahl die Wand nochmal trifft und dann entsprechend eine andere Textur nehmen. Im Grunde ist es so: Wenn die Wand nah ist, dann sieht ein Sichtstrahl nur einen kleinen Teil dieser Wand und stellt diesen dann dar. Der nächste Sichtstrahl trifft aber in der 2D-Matrix genau die gleiche Wand (hier vielleicht mit einer 1 gecodet) muss sie aber ganz anders darstellen von der Textur her... das muss ich jetzt ausarbeiten!

Vielleicht gibt es da auch ganz andere viel bessere und einfachere Lösungen - wenn ja, dann her damit 😉

Das Thema läßt mich gerade nicht los ist aber höchst komplex. Die tollen Vorbilder zeigen aber, daß es mit dem A8 geht und also mache ich weiter. Ich werde für mich jetzt aber etwas den Druck rausnehmen und das ganz entspannt weiterentwickeln bis es gut und schön ist - incl. Texturen...
Das Projekt will ich dann zunächst so weiterentwickeln, das man es als 3D-Engine verwenden kann. Den Code möchte ich final optimieren und dann für alle freigeben...

... mein größtes Problem ist im Moment eigentlich, daß ich nicht genau weiß, wie ich am besten eine Textur zeichnen kann - also mit welchem Programm, wo ich dann die entsprechenden Bitcodes für den Atari bekomme... am besten noch alles auch vergrößern oder verkleinern als Option!

... gerade beim Kaffee ist mir etwas cooles aufgefallen:

Da habe ich ewig mit den Problemen rumgemacht: Wie bestimme ich d - also den Abstand vom Auge zum Treffer in der 2D Matrix und wie korrigiere ich den Effekt der Distorsion - als diesen Fish Eye Effekt. In den Tutorials wird das mit cos tan usw gemacht. Ich habe d zunächst über eine Näherung von Pythagoras berechnet - also statt d = Wurzel aus dxdx+dydy habe ich ja folgendes genommen: d = dy - dx/2 wenn dx dy. Das klappt ganz gut und läßt sich schnell berechnen. Dann kommt je nach Winkel des jeweiligen Sichtstrahls noch die Korrektur der Distorsion: d(korrekt) = cos alpha * d. Dann hat man die korrekte Entfernung. Die Korrektur habe ich via Tabelle gemacht. So weit so gut..... Jetzt habe ich herausgefunden: Das brauche ich alles gar nicht!!! d = dx (für den Fall dx>dy) oder d = dy (für den Fall dx<dy) thats it !!!!!! Nix berechnen, nix nähern! Ich hatte schon die ganze Zeit das Gefühl, daß ich hier zwei Schritte mache, die sich irgendwie am Ende aufheben. Und genau so ist es.

Im Moment hänge ich fest und manchmal hilft es weiter, sich mit anderen auszutauschen! Die Texturen machen mir Schwierigkeiten...

Das Problem ist folgendes: Im Moment berechne ich ja den Abstand d vom Standort des Betrachters in der Matrix zum Wandteil was vom jeweiligen Sichtstrahl getroffen wird. Je nach Abstand zum Wandtreffer wird das Objekt höher gezeichnet (naher Treffer) oder weniger hoch (entfernter Treffer). Nun müsste das Objekt auch in der Breite wachsen oder schrumpfen - je nach Entfernung. Dazu kommt jetzt, daß gerade nahe Objekte von den Sichtstrahlen teil mehrfach getroffen werden - beim Abstand 1 (also ganz nah) bis zu 9 mal. Hier zeichnet er also dann quasi 9 x das gleiche Wandobjekt in entsprechender Höhe. Für diese "Nähe" brauche ich also quasi für das gleiche Trefferobjekt 9 verschiedene Wandteile, die dann nebeneinander gezeichnet werden und die dann eine spezielle Textur (z.B. Steinmuster) ergeben. Gehe ich von der Wand zurück, dann wird das gleiche Wandstück vielleicht nur noch 7 x getroffen und entsprechend muss die gleiche Textur dann halt kleiner mit 7 verschiedenen Wandteilen gezeichnet werden. Diese Wand würde dann ähnlich aussehen nur halt etwas kleiner, was ja auch gewollt ist. Jedes Wandteil ist dann vom Aufbau auch noch abhängig von der Trefferdistanz und entsprechend unterschiedlich. Abgesehen von der erheblichen Speichermenge, muss man diese Wandteile auch erstmal erstellen und in Tabellen vorhalten... und dann richtig ansteuern! Dazu müsste ich auch in der Matrix die jeweilig getroffene Zelle markieren, so daß ich erkenne, ob sie gerade schon getroffen wurde oder nicht. Wenn die gleiche Zelle getroffen wird, dann wird z.B. der 2. Teil der Textur dieser Wand genommen - vorher müsste ich aber auch genau wissen, wie oft denn diese Zelle am Ende wirklich getroffen wird, damit ich entscheiden kann, ob ich von diesem Wandteil den 9 er Block nehme oder z.B. den 7 er .... andererseits müsste schon die errechnete Entfernung d genau das definieren..... alles auf jeden Fall mega aufwendig und ich überlege, ob es nicht viel einfacher ginge... irgendein Kniff. Dass es gut geht, beweisen die Beispiele die schon programmiert worden sind.

Und manchmal nutzt eine gute Näherung viel mehr und funktioniert genauso gut.

Bei der ganzen Überlegung ist mir dann dazu auch noch aufgefaallen, daß meine schöne einfache Theorie mit d und Vermeidung der Distorsion falsch ist. Leider.... wäre auch zu schön gewesen!! d = xneu funktioniert nicht, wenn man sich dreht im Achsensystem der Matrix - man muss tatsächlich über den Pythagoras dx bestimmen und dann via cos alpha die Distorsion rausrechnen: dx = xneu + yneu/2. (wenn yneu < xneu)..... die Näherung für Pythagoras. Dann d = dx * cos alpha Man kann es auch anders machen: beta ist der Winkel des zentralen Sichtstrahls im Koordinatensystem der Matrix und also bekannt: d = xneu * cos alpha / cos (alpha+beta) Der Witz an der Sache ist allerdings: Mein eigentlich falscher sehr einfacher Ansatz für d funktioniert..... ich habe das gerade nochmal getestet und sicherlich sind die Abstände am Ende nicht so ganz richtig, es fällt aber gar nicht auf. Also lasse ich es erstmal und beschäftige mich weiter mit dem Problem der Texturen... vielleicht fällt mir das dann auf die Füße, wenn ich die Texturen erfolgreich umsetze. Vielleicht kann es aber auch so bleiben!

Und genau das ist es mit den Texturen... es muss doch viel einfacher gehen. Irgendwo ist sicherlich ein guter Kniff versteckt, wie ich die Texturen viel einfacher auf die Wände bekomme, als ober angedacht......

Euch einen schönen Sonntag und beste Grüße aus dem sonnigen Hamm! Peter

... so ähnlich war mein Plan. Das Problem ist dann aber noch die schräge Wand. Diese Textur müsste sich dann auch noch in Abhängigkeit der jeweiligen Entfernung ändern... oder ist da mein Denkfehler??

Frohe Deutsche Einheit wünsche ich uns allen!

In den letzten Tagen war ich nicht untätig und habe sehr viel geknobelt, gerechnet, gezeichnet und immer wieder alles in meinen Gedanken hin und her überlegt... In der Summe muss man wohl sagen: Es scheint fast vermessen, einen feinen 3D Shooter mit Raycasting-Technik und Textur für sen A8 hinzubekommen... allerdings gibt es einige Beispiele, die zeigen, daß es eingeschränkt funktionieren kann - das motiviert mich letztlich seit einem halben Jahr und ich habe da ja auch schon ganz gute Fortschritte erzielen können! Die Texturen bringen mich aber echt an Grenzen.... Es scheint fast zu komplex die ganzen Probleme hier so darzustellen, daß man es nachvollziehen kann.

Mein Problem ist der Mehrfachtreffer einer Matrixzelle in Abhängigkeit des Winkels des jeweiligen Sichtstrahls und der Entfernung zum Betrachter. Ein wirklich klares Muster habe ich da nicht finden können und wahrscheinlich gibt es das auch gar nicht... die vielen verschiedenen Treffermuster jedenfalls überschreiten die Kapazität des A8. Da muss ich andere Lösungen finden.

Meine Ausleseroutine ist ok und kann so bleiben - ich werde allerdings noch einen Zähler einbauen, um die Trefferanzahl des jeweiligen Sichtstrahls pro Zelle abzuspeichern. Klingt einfach, ist es aber nicht. Jede Zelle, die getroffen wird muss markiert werden und bei einem weiteren Treffer zählt man die Anzahl - trifft der nächste Sichtstrahl eine andere Zelle, muss die alte Zelle rückgespeichert werden, damit man die Matrix nicht verändert. Das muss ich jetzt als nächsten Schritt umsetzen.

Die anschließende Printroutine - also die optische Ausgabe der 2-D-Matrix als 3-D-Raum auf den Bildschirm muss komplett neu gemacht werden. Im Moment arbeite ich das FieldOfView quasi von links nach rechts ab und zeichne die Mauern mit entsprechender Höhe (je nach Trefferdistanz d) auf den Bildschirm. Diese Methode geht mit der Textur nicht! Ich muss von der Mitte anfangen - also vom Zentralsichtstrahl, von hier zeichne ich erst das FoV nach links - je nach Anzahl der Treffer nehme ich. dann die entsprechende Mauer. Wenn z.B. der Zentralstrahl auf ein Feld 7 x trifft (bedeutet auch die Wand ist nah und wird groß), dann suche ich die Mauer mit 7 Einheiten und zeichne sie. Wenn das Feld daneben z.B. 5x getroffen wird, ist die Höhe der Mauer zwar gleich, die Breite aber nicht, hier nehme ich ein Mauerteil mit entsprechend 5 Teilen... usw. Sobald das FoV links vom Zentrahlstrahl gezeichnet worden ist, muss der Bereich rechts vom Zentrahhlstrahl abgearbeitet werden. Mehr als 9x wird eine Zelle nicht getroffen - jedes Wandteil einer bestimmten Wandart hat also 9 verschiedene Ausprägungen... so könnte es funktionieren.

LG Peter

Guten Morgen in die Runde, seit ein paar Tagen arbeite ich wieder am Raycaster und habe mich erstmal wieder in das Thema eingearbeitet. Kompliziert...

Ich muss die Perspektive noch genauer ausrechnen und brauche dazu zwingend Cosinus - das werde ich mit Tabellen machen- Den Treffpunkt ermittel ich ja mit Bresenham. Der Bresenham macht ja einen Strahl, den ich nicht zeichne, sondern wo ich ständig auslese. Die Länge des Strahls ist dann die Perspektive D, die ich brauche um die Höhe der Mauern zu bestimmen. Diese Perspektive ist aber falsch und muss noch mit cos Winkel des Sichtstrahls etwas reduziert werden.

Jetzt die Frage: Die Länge des Strahls vom Bresenham bestimme ich derzeit über die jeweiligen xEnd-xStart / YEnd-yStart - und davon dann eigentlich mit Pythagoras die Länge bilden... hier nehme ich aber vereinfacht P= dx +dy/2 wenn dy<dx Das muss doch aber einfacher gehen.... kann ich nicht direkt aus dem Bresenham-Algorithmus die Länge bestimmen?? Hat da jemand eine Idee??

Ich habe jetzt nochmal alles ganz anders durchgerechnet und werde mal eine Lösung ohne Pythagoras aber mit Cosinus implementieren. Die Formel dazu habe ich hergeleitet und sieht dann so aus:

Dabei ist alpha der Winkel des Betrachters in der Matrix zu der Matrix und ändert sich entsprechend mit der Drehung des Betrachters. Beta ist der jeweilige Winkel des FieldofView also des jeweiligen Sichtstrahls, der über Bresenham durch die Matrix wandert, bis er auf eine Hindernis trifft. dx ist der Differenzwert - also wieviel in x-Richtung geht der jeweilige Sichtstrahl bis zum Auftreffpunkt.

Um nun die schon korrigierte Distanz (P) zu bestimmen - die dann letztlich für die Höhe der Wand gebraucht wird - brauche ich also nur dx und die beiden Winkel. Die Cosinus Berechnungen muss ich also 2x hintereinander durchführen mit dx * cos(beta) - das wird in einer großen Tabelle bestimmt, der entsprechende Wert muss dann nochmal mit 1/cos(90+beta-alpha) mit einer 2. Tabelle bestimmt.

Das gilt es nun umzusetzen... 😉

.. ach Quatsch Janko, das ist nur Mathe!

Übrigens - die 90 Grad in der Formel kann man noch rausnehmen:

cos (90+beta-alpha) ist nichts anders als sin (beta-alpha)

tatsächlich gibt es noch kleinere Stolperfallen:

Die Formel ist so richtig für den oberen Teil des Zentralsichtstrahles, für den unteren Teil ist es ein wenig anders: Da lautet die Formel:

P = dx * cos beta / sin (beta + alpha) -> für unterhalb des Zentralsichtstrahles P = dx * cos beta / sin (beta - alpha) -> für oberhalb des Zentralsichtstrahles - dabei muss man den Betrag von beta - alpha nehmen

Klingt jetzt zunächst kompliziert und rechenaufwendig, bzw. in Assembler unmöglich - aber für die superschnelle Berechnung nehme ich natürlich Tabellen. Dabei werde ich für den Raycaster ein FoV von ca. 45 Grad haben, also 22,5 Grad über dem Zentralsichtstrahl und 22,5 Grad darunter. Da ich den einzelnen Sichtstrahl jeweils um 2,5 Grad weiterlaufen lasse, brauche ich also 9 verschiedene Winkelberechnungen in der Tabelle. Die möglichen dx Werte kommen ja vom Bresenham und der maximale dx-Wert ist die halbe Breite der Matrix - in meinem Fall vielleicht maximal 25-30. Die 1. Tabelle berechnet also direkt dx * cos beta - bei 9 Winkeln und 30 dx Werten habe ich also ca. 300 Bytes. Die 2. Tabelle wird dann entsprechend den neuen Wert mit mit dem Sinus (beta-alpha) oder Sinus (beta+alpha) ausgeben. Diese Tabelle wird etwas größer sein.

Also folgender Ablauf: Aufbau des FoV:

Der Sichtwinkel im System ist mit alpha bekannt (und ändert sich je nach Drehung des Spielers). Beta von 0 -22,5 Grad nach oben und dann nach unten gibt den Winkel für beta an und läßt den Bresenham in der Matrix laufen. Bei einem Treffer in der Matrix (man fragt ständig ab) wird der dx Wert bestimmt, dann in Tabelle1 dx *cos beta abgefragt, dann in Tabelle2 den aktuellen Wert aus Tabelle1 mit 1/sin(beta-alpha) oder 1/sin (beta+alpha) bestimmen und schon hat man den Wert für die Perspektive P. Die wird gespeichert und nach Durchlauf des gesamten FoV wird dann der Bildschirm gezeichnet. Die Perspektive P bestimmt dann (auch wieder aus einer Tabelle) mit 1/P die Höhe des getroffenen Mauerteils.

Hört sich zunächst alles ganz einfach an, die ganze Umsetzung mit dem Bresenham, der Tabellen, der ganzen Drehung usw. ist schon recht komplex...

... ich hoffe, ich nerve niemanden mit diesem Post um den Raycaster... das Thema ist schon komplex für den A8 ...

Also bei der Umsetzung der 2. Tabelle mit dem 1/sin (beta+alpha) bzw. 1/sin (beta-alpha) bin ich schon auf gewisse "SWchwierigkeiten" gestossen. Ich muss ja hier den Winkel alpha berücksichtigen und jedesmal die Summe bzw. Differenz berechnen... außerdem wird die Tabelle recht mächtig und verbraucht fast 2kB an Speicher. Mit Optimierung (was aber wieder Rechenzeit kostet) komme ich vielleicht auf 1,5 kB. Daher habe ich mich nun doch für einen anderen Weg entschlossen und gehe auf die Berechnung von D (also die Distanz des Bresenham bis zum Hindernis) mittels Pythagoras zurück. Im Prinzip mache ich das auch schon so, habe dafür aber nur eine Näherung: D= dx + dy/2 wenn dx > dy oder D = dy + dx/2 wenn dy > dx. Diese Näherung klappt recht gut und ist schnell, ist aber teilweise recht ungenau.

Ich mache das nun mit einer Tabelle. Da ich ja bereits dx und dy habe, lese ich einfach nur aus einer großen Tabelle den zugehörigen Wert nach Pythagoras je nach dx und dy aus. Diesen ausgelesenen Wert nehme ich für die Cosinus Tabelle und lese den Wert P aus. Die Pythagorastabelle hat dabei einen Umfang von 1-40 für jeweils dx und y also 40 x 40 = 1600 Bytes. Die erste Tabelle musste ich etwas erweitern, da wir nun Werte bis knapp 60 bekommen können in einer Matrix 40 x 40 und verbraucht somit knapp 400 Bytes. Der ganze Prozess kostet mich also etwas 2 kB. Das ist auf jeden Fall vertretbar. Dafür ist die Bestimmung von P exakt und schnell...

... lieben Dank ... nach meiner langen Pause an dem Projekt, brauchte ich auch zunächst etwas Zeit, alles wieder zu durchdringen. Jetzt habe ich wieder alle Gedanken klar 😉

ich möchte mir auch damit etwas Zeit lassen und das ganz ohne Druck weiterentwickeln. An Ende wird man sehen, was dabei rauskommt - gute Beispiele gibt es ja (Capture the flag)- also gehen tut es. Ob ich die Texturen schön hinbekomme, wird man sehen - wenn nicht, dann werden die Wände halt relativ glatt. Sobald der Raycaster mit der neuen Logik gut läuft, werde ich das Projekt umziehen und dann dort weiterberichten. Ich weiß nun mittlerweile auch schon in welche Richtung es gehen soll: Shamus 3D

Ob da jemals etwas spielbares rauskommt wird man dann sehen... vielleicht ja, vielleicht nein 😉

Das Sommerloch, Urlaub, viel Arbeit lassen die Dinge beim Raycaster etwas schleifen. Das Thema ist auch echt komplex - was in Gottes Namen hat mich bloß dazu getrieben dieses Projekt zu versuchen .....

Nebenbei arbeite ich mich ja auf Unity ein. Dies ist ein hochkomplexes Programm - eine 3D Engine - um 3D-Programme später entwickeln zu können. Das schluckt natürlich viel Zeit, aber keine Angst, ich bleibe natürlich dem A8 treu.

Was ich schon echt krass finde ist dieser Unterschied zwischen Raycaster A8 und 3D-Engine auf einem modernen PC. Über 40 Jahre Entwicklungszeit liegen dazwischen. Was mit dem A8 fast unmöglich erscheint und nur mit vielen Tricks und viel viel Gehirnschmalz und Entwicklungszeit vielleicht mit schwacher Grafikqualität geht, das braucht auf Unity vielleicht maximal 20 Minuten, um eine komplette Landschaft mit Texturen zu erstellen, mit Licht und Schatten und mit einem First- oder Third-Kontroller, den man dann sofort durch die Landschaft steuern kann... es ist schon beeindruckend, wie sich das in einer halben Generation entwickelt hat. Werde hier mal vergleichende Bilder posten.

Zu meinem Raycaster: Ich hatte mich jetzt viel mit der geeigneten Grafikstufe beschäftigt, da nichts wirklich optimal ist. Entweder Farben oder Auflösung. Einen Tod muss man sterben. GTIA 10 ist natürlich recht schön mit 9 Farben und hat Scanlinemodus 1 - also in y-Achse hübsch fein aufgelöst, in x-Achse ist es mir aber zu grob. Da haben wir immer 4 Pixel zusammen. Antic D finde ich von der Auflösung besser, da haben wir Scanline 2 - also in x- und y- Achse gleich gut aufgelöst, dafür aber nur 4 (eigentlich nur 3) Farben. Ich glaube dies wurde auch bei Capture The Flag genommen. Capture The Flag ist gut gemacht! Die Wände sind grau und mit schwarz abgesetzt (das ist schlau). Dann hat man noch 2 Farben übrig, eine Farbe für den Boden bzw. Himmel (diese werden dann über DLI´s noch verändert - so daß der mehrfarbige stimmungsvolle Eindruck entsteht), bleibt sogar noch eine Farbe übrig für Items oder andere Wände. Auf eine komplizierte Texture wird verzichtet, das ist auch gut so, dann damit spart man Zeit, Aufwand und optisch ist alles viel besser erkennbar.

So ähnlich versuche ich das nun auch. Thema Texturen: Das ist echt schwierig... ich weiß nicht wirklich, wie man das bei Projekt M gemacht hat. Wird das on the fly berechnet? Oder liegen da viele Tabellen für die verschiedenen Wände in Drehung und Perspektive dahinter? Mit Tabellen würde ich es machen. Ich habe das mal durchgerechnet - Stand jetzt würde das ca. 70kb an Speicher kosten. Geht also rein theoretisch.... ich denke mal, daß die neueren Programme (Doom zB.) das ähnlich lösen, aber da noch etliche gute Optimierungen umgesetzt wurden. 70 kB finde ich jetzt auch deutlich zu viel, da muss ich mir noch gute Tricks bzw. Optimierungen einfallen lassen.

Der Ablauf wird jetzt aber zunächst so sein: Ich werde versuchen die Printroutine komplett neu zu gestalten und den Raycaster ähnlich wie Capture The Flag aussehen zu lassen. Das sieht nämlich optisch sehr schön aus. Sollte ich das zum laufen bringen, versuche ich noch Texturen reinzubringen. Die neue Printroutine werde ich so aufbauen, daß später die Texturen einfacher einzufügen sind. Ich baue also auch jetzt schon ganz Wände bei einem Treffer in Abhängigkeit von Distanz und Winkel.

Dieses Projekt wird sich sicherlich noch über 1-3 Jahre ziehen, denke ich.

Warum wurde Projekt M nie zu einem fertigen Spiel weiterentwickelt und warum zog sich das Projekt M über 10-12 Jahre hin? Weil es so komplex ist. Vielleicht wurden hier auch Videos etwas gefaket... mit Grafik- oder Speichererweiterungen gearbeitet... wer weiß...

Grüße Peter

Das Projekt nähert sich jetzt einem vorläufigen Ende!

Ich baue noch ein wenig an der Routine zum Printen auf den Bildschirm, so daß es etwas bessere Dimensionen hat und besser aussieht und dann ist erstmal gut.

Fazit wird für mich sein: Der A8 ist nicht geschaffen für ein wirklich gutes 3D Spiel wie Doom oder ähnliches. Mit viel Aufwand und intelligenter Programmierung geht es doch (siehe WayOut), es wird aber immer reduziert sein - spätestens bei den Texturen muss man extreme Abstriche machen (Doom für den A8 finde ich nicht spielbar). Einzige wirklich beeindruckende Entwicklung ist m.E. Projekt M bzw. X - warum dieses Projekt sich über fast 15 Jahre hingezogen hat und nie ein richtiges Spiel daraus resultiert ist und nun komplett eingestellt wurde liegt auf der Hand: Die Hardwarekapazitäten wurden wohl alleine für die Demo komplett ausgenutzt, für ein echtes Spiel reicht es dann wohl nicht mehr...

Ich selber bin dann jetzt zufrieden, da ich es hinbekommen habe. Es zu perfektionieren (wie Projekt M) würde mich wohl die nächsten Jahre beschäftigen und mein Kapazitäten komplett binden...

Relativ zeitnah werde ich stattdessen mein nächstes Programm für den Softwarecontest 2025 starten - diesmal wird es ein Jump´nRun werden...

Nach langer Pause überlege ich das Projekt im Herbst - vielleicht zur Fujiama - zu reaktivieren. Einge wichtige Dinge habe ich ja schon umsetzen können, das Projekt bedarf aber einige Anpassungen und kann gerne auch eine längerfristige "Sache" werden... ich habe ja Zeit!!

Ein wichtiger Bestandteil ist ja der Sichtstrahl, den ich mittels Bresenham-Lookup-Tabellen umgesetzt habe. Das war schon eine gute Idee, da es sehr schnell ist. Das Problem war dann immer die Länge des Strahls vom Betrachter zum Aufprall an ein Hindernis zu berechnen. Die einfache Näherung ist schnell und gut, aber durchaus in bestimmten Bereichen recht fehlerhaft. Daher der Versuch der besseren immer noch schnellen fehlerkorrigierten Näherung. Allerdings hatte ich immer das Gefühl, wenn man schon nach dem Bresenham-Algorithmus den Sichtstrahl entlang geht, dann müsste man doch eigentlich quasi als Abfallprodukt auch die Länge des Strahls bekommen. Das geht aber nicht! Selbst ChatGPT hat das erkannt... aber.. da kam mir dann doch die Idee: Bresenham zählt die Steps in x-Richtung und in y-Richtung. Ab und an braucht es dann halt auch einen Step sowohl in x- und y-Richtung. Wenn man jetzt mal die Winkel betrachtet zum Playfield, dann geht der Bresenhamstrahl bei 45 Grad die ganze Zeit in unserer Pixellandschaft schräg. Und die Länge dafür ist √ 2 - warum? Das Pixel ist ein kleines Quadrat mit Seitenlänge 1. Daraus folgt: c^2=1^2+1^2 also c^2=2 und c=√2 Wenn jetzt Bresenham z.B. bis zum Auftreffen auf ein Hindernis (bei 45 Grad) 11x schräg weiterläuft, dann ergibt sich daraus die Länge von L=11 x √2 = 15,6 Bei einem steileren Winkel geht der Strahl vielleicht 3x in x-Richtung und 5x in schräg-Richtung. Die Länge ergibt sich dann wie folgt: L= 3 x 1 + 5 x √2 = 10,1 Bei einem flachen Winkel könnte der Strahl z.B. 8 x in y Richtung laufen und 4 x schräg. Die Länge wäre dann: L= 8 x 1 + 4 x √2 = 13,7 Weil wir immer mit 1 multiplizieren müssen, fällt die Multiplikation einfach weg. Wir müssen also während des Bresenham-Strahls einfach nur geschickt und schnell mitzählen, wie oft sowohl in x- als auch in y-Richtung gelaufen wird (also schräg) und wie oft nur in eine Richtung x oder y. Die Anzahl der Einzelbewegungen werden dann addiert, die Anzahl der Schrägschritte mittels Lookup-Tabelle als Produkt mit √2 dann ebenfalls addiert und schon hat man die so wichtige Länge des Sichtstrahls bis zum Auftreffen auf ein Hindernis (Wand). Keine weiteren Berechnungen mit Pythagoras sind nötig....

Das Programm für den Contest abgegeben - jetzt ist es an der Zeit mal wieder am Ray-Caster zu arbeiten.

Die Erkennung von D, die gesamte Bresenham-Logistik läuft ja schon sehr gut, auch die Routinen für den Sichtstrahl und die Drehung sind praktisch fertig. Mein Problem ist die geschickte grafische Darstellung. Wie bringe ich die Wände so auf den Bildschirm, daß die wie Wände und nicht nur wie einzelne frontal stehende Mauern aussehen?? Ich habe jetzt die Printroutine komplett neu überarbeitet - sie läuft jetzt auch schneller und es sieht schöner aus, aber das eigentliche Problem habe ich damit nicht gelöst.

Ich habe mir jetzt seit Tagen den Kopf zerbrochen und werde jetzt eine ganz andere Idee als nächstes umsetzen. Ich definiere in der Matrix zusammenhängende Mauerteile und werde diese dann vom Startpunkt der Mauer links oben bis zum Endpunkt rechts oben einfach wieder mit dem Bresenham Algorithmus zeichnen. Die Mauerteile dazwischen sind dann nicht relevant und geben nur noch die Breite an. So bekomme ich dann eine schöne zusammenhängende obere (und untere) Abschlußkante. Die Mauer hat zunächst keine Textur.

Ich werde das jetzt vorbereiten und auf der Fujiama dann mit viel Zeit hoffentlich weiterentwickeln...

... da hatte ich auf der Fujiama andere Dinge und zunächst habe ich noch einen weiteren Ansatz verfolgt, um die Mauern besser zeichnen zu können. Mit etwas besserer Auflösung. Aber auch das löst mein Problem nicht. Die Auflösung ist einfach in der Matrix nicht fein genug und die Mauern werden so nie schön homogen gezeichnet. Also mache ich jetzt den nächsten Versuch - wie oben beschrieben - ich analysiere den Anfangspunkt und Endpunkt der Mauer in der Matrix und zeichnen dann via Bresenham die Linien der Maueroberkante - spiegel es nach unten und fülle den Zwischenbereich. Auf eine mögliche Textur verzichte ich jetzt erstmal - vielleicht gibt es später noch gute Lösungen. Am Ende muss es ja auch mit der Geschwindigkeit passen.

Ich benutze in der Matrix schon die Bresenham-Logik (für den Vorantrieb des Sichtstrahles) - aber nicht als Berechnung, sondern als schnelle Tabelle. Also mein Bresenham steckt in einer großen Tabelle. Diese Tabelle möchte ich auch für die Linienzeichnung nutzen und hier habe ich mir ein paar Gedanken machen müssen. Am Ende habe ich ja zwei unterschiedliche Höhen mit einem definierten Abstand x und die Idee ist eine weitere Tabelle, die dann zum Bresenhamvektor führt. Diese Tabelle ist recht lang und das habe ich die letzen Wochen entwickelt. Nun muss ich das hier eingeben, noch ein wenig anpassen und kann dann die Linien schnell zeichnen.

Die gesamte Erkennungsroutine und Plotroutine muss dabei praktisch neu programmiert werden.... das wird sich bei meinem Zeitmangel bestimmt bis ins Frühjahr hinziehen weil aufwendig und komplex!!!

Soweit mal ein Lebenszeichen von mir...

... zwischen den Tagen habe ich die neuen Tabellen fertig stellen können, vorgestern dann die Bresenhamkonvertierungstabelle ins Programm eingepflegt und heute habe ich dann die entsprechende komplexe Routine gebaut. Die gute Nachricht: Die Routine funktionierte erstaunlicherweise sofort... und ich bin auf dem richtigen Weg. Es sind noch etliche Fehler in der Plotroutine und da muss noch einiges angepasst werden, aber in dem kleinen Beispiel sieht man, daß der Weg richtig ist. Endlich kann ich die Wände (auch schräg) richtig zeichnen und die Geschwindigkeit ist enorm hoch...

Aber da hängt noch viel viel Arbeit. Ich hätte echt nicht gedacht, daß der Raycaster so schwierig und aufwendig wird...

.... nun habe ich ein wenig mit der Darstellung "rumgemacht" und habe da leider noch ganz erhebliche Fehler in der Darstellung. Ganz genau weiß ich noch nicht, womit alle Fehler zusammenhängen, ein paar habe ich allerdings schon lokalisiert. Insgesamt muss man sagen, daß der neue Weg wohl richtig ist, da er die Wände besser zeichnet, dafür ist das System viel fehleranfälliger - bedeutet, daß kleine Fehler wenig gut toleriert werden. Die Beschreibung der Raycaster Systematik beinhaltet immer auch die Distorsion und ich hatte gehofft, daß es bei mir nicht relevant ist - im Gegenteil. Ich brauche tatsächlich zwingend die Eliminierung der Distorsion. Jede errechnetet Distanz muß also noch mit cos(winkelzumhauptstrahl) multipliziert werden. Beispiel: der Hauptsichtstrahl trifft die Wand und die Distanz beträgt z.B. 6 - ich muss dann mit cos(0) multiplizieren und erhalte 6 ... der 8. Strahl nach rechts z.B. wäre ja in meinem Fall (jeder FOV-Strahl wandert um 2,5° weiter) bei 20° - blicke ich genau senkrecht auf die Wand, dann habe ich eine rechnerische Distanz bei 20° im FOV von etwa 6,4 -> 6,4 x cos(20) = 6 Wenn ich schräg auf die Wand schaue, dann kommen natürlich unterschiedliche Werte für die Wandhöhen und entsprechend wird die Wand schräg gezeichnet, die Distorsion muss aber auch hier zwingend rausgerechnet werden... wenn von Interesse, stelle ich hier noch ein paar Zeichnungen mit Berechnungen rein (alle schön handschriftlich).

Ich brauche nun also eine Tabelle für cos (alpha). Winkel habe ich von 0-20 ° pro Seite bei einem FOV von 40°. Da brauche ich also 8 verschiedene cosinus - Winkelwerte, bei Distanzen von 1-30 mit denen ich multiplizieren muss, macht das dann also eine Tabelle von ca. 8x30 also etwa 300 Byte... das geht ja noch!

Das wird also als nächstes umgesetzt... 😉

Hallo Wolfram, zu deiner Frage:

Ray Casting bedeutet im Prinzip eine 3-dimensionale Darstellung einer 2-Matrix. Also man hat eine 2-d-Matrix und in dieser Matrix bewegt sich der Player. Der Player schaut in dieser Matrix nach vorne und hat einen Blickwinkel (FOV = field of view). Das FOV eines Players hat üblicherweise so 40-50 Grad. Es gibt also x- Sichtstrahlen, die das Programm abarbeiten muss. Der Haupsichtstrahl schaut also nach vorne und in der 2-d-Matrix läuft der Sichtstrahl nach vorne. Trifft er auf ein Hindernis (Mauer), dann ist das ein Treffer mit einer Distanz von dort wo der Player steht zum Hindernis. Je größer die Distanz ist, desto kleiner ist die Wand. So wird nun 20 Grad nach links und 20 Grad nach rechts das FOV abgearbeitet. Für jeden Sichtstrahl erhält man eine Treffer einer bestimmten Distanz. Diese Distanzen sind dann umgerechnet die einzelnen Höhen der getroffenen Mauern und dies printet man dann auf den sichtbaren Bildschirm. Es entsteht dann ein räumliches Bild wie z.B. bei Doom oder Wolfenstein, Way-Out oder wie sie alle heißen. Ray-Casting ist also die Idee aus einer 2-d-Matrix einen Raum zu generieren... Ich hoffe das war so einigermaßen verständlich... Das Problem ist halt, daß ein 8-Bit-Rechner dafür nicht wirklich gut geeignet ist... es fehlt die Auflösung, der mathematische Co-Prozessor, die Geschwindigkeit, die Fließkommamöglichkeit in Assembler usw. Alles muss in Assembler passieren, weil man in Basic viel zu langsam wäre - man braucht etliche mathematische Rechenfunktionen (Cosinus, Pythagoras, Fließkomma, 1/x ) muss also ganz viel tricksen... LG Peter

Oh Mann ... mit der Zeit wird man wohl auch "programmierblind"...

gerade habe ich erkannt, wo wohl mein Hauptproblem die ganze Zeit liegt und warum ich ums verrecken die 3D Darstellung nicht gut und sauber hinbekomme. Mir war ja im Prinzip schon immer klar, daß ein Hauptproblem der fehlende mathematische Coprozessor ist und damit die im Assembler fehlende Fließkommaberechnung ein echtes Problem ist. Dazu natürlich die Geschwindigkeit bei allen Berechnungen. Das ist der Grund für die ganzen Tabellen - hier muss man ja nicht rechnen und am Ende wird eh alles auf ganze Zahlen gerundet. Und hier ist der entscheidende Fehler:

Folgender Ablauf zur Zeit: 1. Ein Sichtstrahl trifft auf eine Wand. Anhand der x- und y-Position wird mittels einer Tabelle die Distanz berechnet (Pythagoras). Die Distanz wird als gerade Zahl in der Tabelle angegeben also aufgerundet. 2. Die Distorsion wird mittels einer Tabelle rausgerechnet. Hier wird wieder aufgerundet. 3. Der Wert wird nun umgekehrt ( 1/x) und mit einem Faktor ( ca. 20) multipliziert. Das ist notwendig, da ein großes D (Distanz) eine kleine Wand bedingt (weit weg) und umgekehrt. Der Faktor passt dann nur noch die Wandhöhe an den Bildschirm an.

Es wird also 2x vorher gerundet und wegen des Faktors (ca. 20) wird dann der Rundungsfehler sehr unterschiedlich ausfallen. Ich checke jetzt mal, ob ich aus den drei Tabellen eine einzige mache, wo dann wirklich nur ganz am Ende die Auf-/Abrundung passiert. Das hätte erhebliche Vorteile was Speicher, Geschwindigkeit und Genauigkeit angeht...

Hallo Bernhard, schau doch bitte mal die Posts vorher an - hier habe ich mehrfach Skizzen und Berechnungen eingestellt - da wirst es dann erkennen. Und ja, es ist immer Pythagoras gefordert - alternativ kann man es mit Cosinus und Sinus auch machen, was die Sache aber nicht einfacher machen würde. LG Peter

... wir bewegen uns natürlich "nur" bei Zahlen (Distanzen) zwischen 1 (minimale Entfernung) und 42 (maximale Distanz). Der Gesamtfehler ist dann relativ klein, führt aber dennoch zu blöden Effekten beim Print...

Die Idee ist also nun eine Tabelle zu machen, wo alles schon direkt berechnet wird und die Rundung nur ganz am Ende auftritt. Der Fehler ist dann minimiert. Das Problem ist allerdings die Distorsion, die ich zwischendrin rausrechnen muss. Und die ist vom Winkel abhängig. Ich nutze ein maximales FOV von 40 Grad - also jeweils 20 Grad in eine Richtung. Mein Sichtvektor geht alle 2,5 Grad weiter, ich müsste dann also theoretisch 9 verschiedene Tabellen â 30x30 Bytes generieren. Das sind dann etwa 8 kB. Kann man machen, ist aber wirklich aufwendig. Zum Glück allerdings ist die Distorsion bin einschl. 10 Grad zu vernachlässigen (cos 10 = 0,98) also starte ich erst ab 12,5 Grad und brauch dann nur 5 statt 9 Tabellen - immerhin noch ca. 4,5 kB. Dafür muss ich gar nichts mehr berechnen und habe direkt aus der Distanz die Wandhöhe.

Was jetzt leider noch fehlt: Ich habe bislang das FOV ganz stur von -20 Grad bis +20 Grad Strahl für Strahl abgearbeitet. Das ist problematisch und gibt verzerrte Werte. Ich muss es immer vom Hauptsichtstrahl machen - also von 0 Grad bis -20 Grad und dann von 0 Grad bis +20 Grad. Das wird etwas komplizierter zu programmieren und ich muss die komplette Routine quasi neu schreiben...

darüber habe ich tatsächlich auch nachgedacht, eine Stelle nach dem Komma würde ja auch durchaus reichen... das Problem ist dann aber immer noch die Geschwindigkeit. Ich könnte dann zwar einigermaßen ausreichend "rechnen" - wobei die Distorsion mit D x cos (alpha) würde ich trotzdem mittels Tabelle bestimmen müssen - aber das würde deutlich mehr CPU-Last bedeuten.

... ja klar, aber beim Raycasting ist am Ende alles so zeitkritisch, daß ich besser gar nichts rechne...

Im Grunde ist der Ablauf folgender:

Da ist diese 2D-Matrix â 30x30 Größe. In dieser Matrix sind Wände und irgendwo der Player. Der Player läuft in dieser 2D-Matrix herum und kann sich jeweils nach rechts oder links drehen, nach vorne oder nach hinten bewegen. Der Player schaut nach vorne und hat ein FOV (field of view) von 40 Grad. Insgesamt nutze ich dann 19 Sichtstrahlen in einem Winkel von je 2,5 Grad - also von 0 (Hauptsichtstrahl nach vorne) nach -20 Grad (das sind dann 8 Blickstrahlen -2,5 Grad, -5 Grad ... -20 Grad, 0 Grad, 2,5 Grad ... 5 Grad .... 20 Grad) also 19 Sichststrahlen. Alle diese 19 Strahlen laufen nacheinander nach vorne bzw. schräg vorne (hier braucht man den Bresenham-Algorithmus) bis jeweils ein Treffer erfolgt. Anhand des x- und y-Wertes wird dann mit Pythagoras die Distanz berechnet, mit cos Blickwinkel dann die Distorsion korrigiert und dann kommt noch 1/x (nah dran kleiner Wert = hohe Mauer) x ein Faktor (ich nehme 40 - hängt von der Bildschirmauflösung dann ab). Dies wird also alles 19x durchlaufen und berechnet und abgespeichert und im nächsten Schritt wird dann diese Block der 19 Distanzen auf den Bildschirm gezeichnet uns so entsteht dann aus der 2D-Matrix ein 3D-artiges Bild ... und alles quasi in Echtzeit. Bei jeder Joystickbewegung muss das komplett durchgeführt werden! Da kann man nicht viel rumrechnen mit unserer kleinen 6502 CPU 😉

Hallo Sascha, interessante Idee, aber ich glaube das geht nicht. Die Datenmengen, die du vorberechnen müsstest wäre einfach zu groß. Alle Wände müssten ja hinsichtlich Höhe, Breite, Winkelung vorberechnet werden. Ich habe mich allerdings tatsächlich mit der Idee grundsätzlich beschäftigt, da ich so etwas ähnliches bei einer Textur brauchen könnte. Wände in verschiedenen Höhen mit unterschiedlichen Winkelungen... das habe ich mal in etwa kalkuliert - und würde bei mind. 70-90 kb landen... LG Peter

Hallo in die Runde, ich möchte jetzt meine Hauptroutine umbauen... eine Problematik habe ich dabei zwar gelöst und umgesetzt, aber das würde ich gerne effiktiver machen! Folgendes Problem: Ich habe mein FOV von 40 Grad und dieses FOV besteht aus dem Hauptsichstrahl nach vorne und jeweils 8 Sichtstrahlen nach links und nach rechts mit einem Winkel um 2,5 Grad. So wird das FOV abgearbeitet. Der Spieler (also das FOV) dreht sich in der 2D-Matrix um 360 Grad und je nach Position wird in einer Tabelle ein unterschiedlicher Bresenham-Zug geladen und verarbeitet. Die Nummern der "Züge" sind in einer Tabelle von 0 (0 Grad) bis 144 (360 Grad) gespeichert und die Rotationsposition von 0 - 144 in einer Variablen abgelegt. Ein Problem bekomme ich immer, wenn ich von 144 wieder auf 0 springe oder von 0 auf 144 (je nach Drehung), da damit das FOV quasi auseinandergerissen wird. Ich bräuchte eigentlich eine endlose Tabelle, die diese Kreisbewegung abbildet. Im Moment umgehe ich das, indem ich die 144 20x wiederhole... da muss es doch eine schlauere Idee geben? Wer hat Ideen? LG Peter